"""
2749. 得到整数零需要执行的最少操作数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。



示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。
示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。


提示：

1 <= num1 <= 109
-109 <= num2 <= 109
"""
from itertools import count


class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        """
        思路 num1每次减去num2，看二进制有多少个1，当1的数量小于次数，即为最小
        :param num1:
        :param num2:
        :return:
        """
        n = 0
        while True:
            #n的要大num1.bit_count的1次数，同时他们能组成num1.bit_count（num1>=n）
            if num1>=n and n >= num1.bit_count():
                return n
            if num1<n:
                return -1
            num1 -= num2
            n+=1
        return -1

    def makeTheIntegerZero_re1(self, num1: int, num2: int) -> int:
        for k in count(1):  # 枚举 k=1,2,3,...
            x = num1 - num2 * k
            if k > x:
                return -1
            if k >= x.bit_count():
                return k

if __name__ == '__main__':
    # print(Solution().makeTheIntegerZero(5,7))
    # print(Solution().makeTheIntegerZero(110,55))
    print(Solution().makeTheIntegerZero(3,-2))#3
    print(Solution().makeTheIntegerZero_re1(3,-2))#3
    print(count(1))